package 算法;



/**
 * ⼀只⻘蛙⼀次可以跳上1级台阶，也可以跳上2级。求该⻘蛙跳上⼀个n级的台阶总共有多少种跳法并列举
 * 这里用的递归运算，递归的核心是递去，归来。思想应该是去分析归来，因为递去是复杂的（递去可以看做归来的准备）
 *
 * 参考地址：非常详细，只不过他只求了多少种跳法，没有列举，但方法是一样，会给一种醍醐灌顶的感觉
 * https://mp.weixin.qq.com/s?__biz=Mzg2NzA4MTkxNQ==&mid=2247485287&amp;idx=1&amp;sn=334ca94218932fdb3bd60684f159a8bd&source=41#wechat_redirect
 *
 */
public class 台阶问题 {
    public static int i = 1;
    public static  int co = 0;

    public static void main(String[] args) {
        System.out.println(jump(4,""));
        System.out.println(jumpCount(4));
    }
    public int climbStairs(int n) {
        if(n <= 2) return n;
        int[][] map = new int[2][n];
        map[0][0] = 1;
        map[0][1] = 1;
        map[1][0] = 0;
        map[1][1] = 1;
        for(int i = 2; i < n; i++){
            map[0][i] = map[0][i-1] + map[1][i-1];
            map[1][i] = map[0][i-2] + map[1][i-2];
        }
        return map[0][n-1]+map[1][n-1];
    }
    //返回跳的结果
    public static String jump(int coun, String sb){
        co++;
        if(coun < 1){
            System.out.println("第"+i+++"种方法"+sb);
            return "";
        }else if(coun>1){
             jump(coun-2,"->2"+sb);
        }
             jump((--coun),"->1"+sb);

        return "运行了 "+co;
    }
    //跳的次数，这里用的斐波那契数列

    public static int jumpCount(int n){
        if(n <= 2){
            return n;
        }
        int f1 = 0;
        int f2 = 1;
        int sum = 0;
        for(int i = 1; i<= n; i++){
            sum = f1 + f2;
            f1 = f2;
            f2 = sum;
        }
        return sum;
    }
}
